1. Field of the Invention
The present invention is directed to a method of converting color data from one color space or coordinate system to another color space or coordinate system using convex interpolation and, more particularly, to determining whether a color value, point or signal to be interpolated is within a convex hull of the color values, points or signals in the neighborhood of the point in a first color space and, if so, determining the interpolation weights required to obtain the corresponding target color value in the second space using the points in the second space that correspond to the surrounding points in the first space.
2. Description of the Related Art
Interpolation using look-up tables (LUT) is an approach used for color calibration in both transforming color signals from one color space to another color space and in creating tables used for such transformations. A basic goal in color calibration is to reproduce color images generated from one device on another device without loss or with minimum loss of color fidelity. FIG. 1 illustrates a color calibration process to reproduce a color image for device I on device II. In FIG. 1, the input image is represented in a device-dependent color space (DDCS1) 10, the output image is represented in another device-dependent color space (DDCS2) 12, the transformation between DDCS1 and DDCS2 is performed through a device-independent color space (DICS) 14.
The relationship between a DDCS and a DICS can be described by a LUT which is obtained by measuring a number of color patches generated from the specific device. For convenience, the code values of these color patches are usually chosen to be lattice points spanning the full range of the DDCS, while their corresponding points in the DICS may be spaced irregularly. An interpolation from a DDCS to a DICS is a called forward interpolation, and an interpolation from a DICS to a DDCS is called a backward interpolation as illustrated in FIG. 2.
We now consider the following general interpolation problem. Let X={x.sub.1, x.sub.2, . . . , x.sub.s } be a set of points in a n-dimensional vector space R.sup.n (s &gt;n), and Y={y.sub.1, y.sub.2, . . . y.sub.s } be a set of the corresponding points in a m-dimensional vector space R.sup.m. The sample set of (x.sub.1, y.sub.1), . . . , (x.sub.s, y.sub.s) is called a look-up table (LUT). Given a point x.epsilon.R.sup.n, we want to find its corresponding point y.epsilon.R.sup.m by interpolation based on the LUT.
Multi-dimensional interpolation is a common problem in computational geometry, computer graphics, and color calibration. Most of the existing interpolation methods are designated for the cases in which the sample points x.sub.1, x.sub.2, . . . , x.sub.s are lattice points in R.sup.n and, as a result, cannot be used for backward interpolation since the points in the LUT are non-lattice points in the DICS. Among these forward interpolation schemes are the 4-point tetrahedron interpolation, the 6-point prism interpolation, and the 8-point cube interpolation, also known as the trillnear interpolation. More general interpolation methods which do not require that x.sub.1, x.sub.2, . . . , x.sub.s be lattice points in R.sup.n include the vector interpolation, the distance-based interpolation and the tetrahedral interpolation. In the vector model, a linear function is used to interpolate a point x=(z.sub.1, z.sub.2, z.sub.3).sup.T (where T denotes the transpose of a vector): EQU y=f(x)=a.sub.1 z.sub.i +a.sub.2 z.sub.2 +a.sub.3 z.sub.3 +a.sub.4( 1)
where the coefficients a.sub.1, a.sub.2, a.sub.3, a.sub.4 .epsilon. R.sup.3 are determined so that f(x) satisfies the following boundary conditions: EQU f(x.sub.i)=y.sub.i, i=1,2,3,4, (2)
where x.sub.1, x.sub.2, x.sub.3, x.sub.4 .epsilon. R.sup.3 are the four points closest to x in X, y.sub.1, y.sub.2, y.sub.3, y.sub.4 are the corresponding points of x.sub.1, x.sub.2, x.sub.3, x.sub.4. A problem with this model is that it sometimes gives an interpolated point y which is far from all the points y.sub.1, y.sub.2, y.sub.3, y.sub.4. A distance-based model interpolates a point x based on the distances between x and k points x.sub.1, x.sub.2, . . . , x.sub.k closest to x: ##EQU1## where y.sub.1, y.sub.2, . . . y.sub.k are the corresponding points of x.sub.1, x.sub.2, . . . , x.sub.k, and ##EQU2## where .parallel...parallel. denotes the Euclidean distance, p is usually set to be 2. A problem with this interpolation scheme is that when x is close to a sample point x.sub.i, the weight or coefficient w.sub.i becomes dominant, resulting in a flat region in the neighborhood of y.sub.i. A common problem with both the vector interpolation and the distance-based interpolation schemes is that the sample points used for interpolation are selected based on distance only. This could lead to a situation in which the interpolation formulas are used for an extrapolation problem as indicated by FIG. 3. This can happen simply because k points closest to a given point x may not necessarily surround x as illustrated in FIG. 3. Tetrahedral interpolation requires using surrounding points for the interpolation, but restricts use to only n+1 points during interpolation in an n-dimensional interpolation problem. This makes tetrahedral interpolation sensitive to noise and less robust. In addition tetrahedral interpolation requires three steps in the process. The first step is to find a tetradehedron which encloses the given point, the second step is to determine the interpolation coefficients and the third step is to interpolate. The overhead computation involved reduces the efficiency of the interpolation scheme.
What is needed is a more powerful interpolation method to map color signals between color spaces.